package 记忆化搜索;

import java.util.Arrays;

//64 最小路径和
public class Solution6 {
        public int minPathSum(int[][] grid) {
            int row = grid.length;
            int col = grid[0].length;
            mem = new int[row][col];
            for (int i = 0 ; i <  row ; i++) Arrays.fill(mem[i], -1);
            return dfs(0,0,row,col,grid);
        }
        int[][] mem;
        private int dfs(int i,int j,int row,int col,int[][] grid) {
            if (i == row - 1 && j == col - 1) {
                return grid[i][j];
            }
            if (i < 0 || j < 0 || i >= row || j >= col) return 1000000;
            if (mem[i][j] != -1) return mem[i][j];
            int ans = Math.min(dfs(i + 1, j, row, col, grid), dfs(i, j + 1, row, col, grid)) + grid[i][j];
            mem[i][j] = ans;
            return ans;
        }
}
